package core;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

import functions.Function;
import functions.FunctionIF;
import functions.PolynTerm;

public class NewtonDividedDifferences extends InterpolatingMethod {

	@Override
	public Function run(Point[] points) {
		LinkedList<Point> xPoints = new LinkedList<Point>();
		LinkedList<Point> yPoints = new LinkedList<Point>();
		for (int i = 0; i < points.length; i++) {
			Point x = new Point(points[i].getX());
			Point y = new Point(points[i].getY());
			xPoints.add(x);
			yPoints.add(y);
		}
		return solution(xPoints, yPoints);
	}
	
	
	
	public Function solution(LinkedList<Point> xPoints,
			LinkedList<Point> yPoints) {
		
		@SuppressWarnings("unchecked")
		LinkedList<Point>[] list = new LinkedList[xPoints.size() + 1];
		list[0] = xPoints;
		list[1] = yPoints;
		for (int i = 2; i < list.length; i++) {
			list[i] = new LinkedList<Point>();
		}
		for (int i = 1; i < list.length; i++) {
			for (int j = 0; j < list[i].size() - 1; j++) {
				double temp = (list[i].get(j).getX() - list[i].get(j + 1)
						.getX())
						/ (list[0].get(j).getX() - list[0].get(j + i).getX());
				Point p = new Point(temp);
				list[i + 1].add(p);
			}
		}
		
		Function f = new Function();
		
		for (int i = 1; i < list.length; i++) {
			ArrayList<FunctionIF> product = new ArrayList<FunctionIF>();
			
			product.add(new PolynTerm(list[i].get(0).getX(), 0));
			
			Iterator<Point> itr= xPoints.iterator();
			for(int k = 1 ; k < i ; k++)
				product.add(getTerm(itr.next().getX()));
		}
		
		return f;
	}
	
	private FunctionIF getTerm(double x)
	{
		Function f = new Function();
		ArrayList<FunctionIF> p = new ArrayList<FunctionIF>();
		p.add(new PolynTerm(1, 1));
		f.addProductTerm(p);

		ArrayList<FunctionIF> p1 = new ArrayList<FunctionIF>();
		p1.add(new PolynTerm(-x, 0));
		f.addProductTerm(p1);
		return f;
	}
	
	public static void main(String[] args) {
		NewtonDividedDifferences NDD = new NewtonDividedDifferences();
		//test#1
//		Point p0 = new Point(3.2, 22);
//		Point p1 = new Point(2.7, 17.8);
//		Point p2 = new Point(1, 14.2);
//		Point p3 = new Point(4.8, 38.3);
//		Point p4 = new Point(5.6, 51.7);
//		Point[] points = { p0, p1, p2, p3, p4 };
		//test#2
		Point p0=new Point(8,-0.145500034);
		Point p1=new Point(2,-0.416146837);
		Point p2=new Point(4.6,-0.112152527);
		Point p3=new Point(3.6,-0.896758416);
		Point p4=new Point(3.14,-0.999998732);
		Point p5=new Point(1.7,-0.128844494);
		Point p6=new Point(0,1);
		Point p7=new Point(1.34400, 0.22485705);
		Point p8=new Point(3,-0.989992497);		
		Point[] points = { p0, p1, p2, p3, p4,p5,p6,p7,p8};
		NDD.run(points);
		
	}

}
